UVa/10482 - The candyman can/jesus.federico.cpp

   1 #include<iostream>
   2
   3 using namespace std;
   4
   5 int n,CASO,T[100],mem[55][55][55][40],INF;
   6
   7 int dp(int a, int b, int c, int voy)
   8 {
   9     if(a>51||b>51||c>51)
  10         return 1<<30;
  11
  12     if(voy==n)
  13         return max(a,max(b,c));
  14
  15     if(mem[a][b][c][voy]!=INF)
  16        return mem[a][b][c][voy];
  17
  18     int na,nb,nc,mimin,s=1<<30;
  19
  20     na=a,nb=b,nc=c;
  21     na+=T[voy];
  22     mimin=min(na,min(nb,nc));
  23     s<?=dp(na-mimin,nb-mimin,nc-mimin,voy+1);
  24
  25     na=a,nb=b,nc=c;
  26     nb+=T[voy];
  27     mimin=min(na,min(nb,nc));
  28     s<?=dp(na-mimin,nb-mimin,nc-mimin,voy+1);
  29
  30     na=a,nb=b,nc=c;
  31     nc+=T[voy];
  32     mimin=min(na,min(nb,nc));
  33     s<?=dp(na-mimin,nb-mimin,nc-mimin,voy+1);
  34
  35     return mem[a][b][c][voy]=s;
  36 }
  37
  38 int main()
  39 {
  40     cin>>CASO;
  41
  42     for(int i=1;i<=CASO;i++)
  43     {
  44         cin>>n;
  45
  46         for(int j=0;j<n;j++)
  47             cin>>T[j];
  48
  49         memset(mem,-1,sizeof(mem));
  50         INF=mem[0][0][0][0];
  51
  52         printf("Case %d: %d\n", i, dp(0,0,0,0));
  53     }
  54
  55     return 0;
  56 }